package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3

/**
 * https://leetcode.cn/problems/delete-leaves-with-a-given-value/description
 *
 * 题型： 二叉树的后序遍历 + 分治法
 *
 * ```
 * 1325. 删除给定值的叶子节点
 * 给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。
 * 注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。
 * 也就是说，你需要重复此过程直到不能继续删除。
 *
 * 示例 1：
 * 输入：root = [1,2,3,2,null,2,4], target = 2
 * 输出：[1,null,3,null,4]
 * 解释：
 * 上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。
 * 有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。
 *
 * 示例 2：
 * 输入：root = [1,3,3,3,2], target = 3
 * 输出：[1,3,null,null,2]
 *
 * 示例 3：
 * 输入：root = [1,2,null,2,null,2], target = 2
 * 输出：[1]
 * 解释：每一步都删除一个绿色的叶子节点（值为 2）。
 *
 *
 * 提示：
 * 树中节点数量的范围是 [1, 3000]。
 * 1 <= Node.val, target <= 1000
 * ```
 */
class leetcode_1325 {
    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n3_2 = TreeNode(3)
        val n3_3 = TreeNode(3)
        val root = n1
        n1.left = n3
        n1.right = n3_2

        n3.left = n3_3
        n3.right = n2

        val actual = removeLeafNodes(root, 3)
        val expected = arrayListOf(1, 3, null, null, 2)
        Assert.assertEquals(expected.toString(), printLevelOrder3(actual).toString())
    }

    fun removeLeafNodes(root: TreeNode?, target: Int): TreeNode? {
        /**
        题型： 二叉树的后序遍历 + 分治法

        思路：
        递归左子树，得到新左子树
        递归右子树，得到新右子树

        若当前节点 等于 target，且新左子树和右子树均为null，那么，当前节点才会被删除，则返回null，否则返回当前节点

         */
        // 1 确定函数的参数以及返回值

        // 2 确定终止条件
        if (null == root) {
            return null
        }

        // 3 确定单层递归的处理逻辑: 后序遍历

        // 左
        root.left = removeLeafNodes(root.left, target)

        // 右
        root.right = removeLeafNodes(root.right, target)

        // 中
        // 根据示例2： 若当前节点等于target，只有新左右孩子均为null，当前节点才会被删除。
        if (root.`val` == target && root.left == null && root.right == null) {
            return null
        }

//        if(root.`val` == target){
//            if(root.left == null && root.right == null){
//                return null
//            }
//            else{
//                return root
//            }
//        }

        return root
    }
}